#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;

const int INF = 0x3f3f3f3f;
const int r[] = { 1,0 };
const int MAX_DEPTH = 10;
const int SIZE = 3;

char chess[SIZE][SIZE] = { 0 };

int alphabeta(int depth, int alpha, int beta, int move, int & x, int & y);
bool owin();
bool xwin();
void scanInput();
int evaluate(int move);
int count_ones(int num);
void print_board();

int main()
{
	int move;
	int remain = SIZE * SIZE;

	printf("choose mode(0 for computer first, 1 for human first): ");
	cin >> move;

	while (!xwin() && !owin() && remain)
	{
		if (move == 1)
		{
			scanInput();
			move = 0;
		}
		else if (move == 0)
		{
			int bestX, bestY;

			alphabeta(min(remain, MAX_DEPTH), -INF, INF, 0, bestX, bestY);
			printf("computer input: %d %d\n", bestX, bestY);

			chess[bestX][bestY] = 'x';

			move = 1;
		}
		print_board();
		remain--;
	}

	if (xwin())
		printf("computer wins\n");
	else if (owin())
		printf("human wins\n");
	else
		printf("no one wins\n");

	return 0;
}

bool xwin()
{
	int mask = (1 << (2 * SIZE + 2)) - 1;
	for (int i = 0; i < SIZE; i++)
	{
		for (int j = 0; j < SIZE; j++)
		{
			if (chess[j][i] != 'x') mask = ~((~mask) | (1 << j));
			if (chess[i][j] != 'x') mask = ~((~mask) | (1 << (SIZE + j)));
		}
		if (chess[i][i] != 'x') mask = ~((~mask) | (1 << (2 * SIZE)));
		if (chess[i][SIZE - 1 - i] != 'x') mask = ~((~mask) | (1 << (2 * SIZE + 1)));
	}
	return mask;
}

bool owin()
{
	int mask = (1 << (2 * SIZE + 2)) - 1;
	for (int i = 0; i < SIZE; i++)
	{
		for (int j = 0; j < SIZE; j++)
		{
			if (chess[j][i] != 'o') mask = ~((~mask) | (1 << j));
			if (chess[i][j] != 'o') mask = ~((~mask) | (1 << (SIZE + j)));
		}
		if (chess[i][i] != 'o') mask = ~((~mask) | (1 << (2 * SIZE)));
		if (chess[i][SIZE - 1 - i] != 'o') mask = ~((~mask) | (1 << (2 * SIZE + 1)));
	}
	return mask;
}

void scanInput()
{
	int x, y;
	bool valid = false;

	printf("input: ");
	while (!valid)
	{
		cin >> x >> y;
		if (!(x >= 0 && x < SIZE && y >= 0 && y < SIZE) || chess[x][y] != 0)
		{
			printf("input not valid, try again: ");
		}
		else
			valid = true;
	}

	chess[x][y] = 'o';
}

int alphabeta(int depth, int alpha, int beta, int move, int & x, int & y)
{
	if (xwin())
	{
		return move ? -INF : INF;
	}
	if (owin())
	{
		return move ? INF : -INF;
	}
	if (depth == 0)
	{
		//return evaluate(move);
		return 0;
	}

	int placeholder;
	int bestX = -1, bestY = -1;
	for (int i = 0; i < SIZE; i++)
	{
		for (int j = 0; j < SIZE; j++)
		{
			if (chess[i][j] == 0)
			{
				chess[i][j] = move ? 'o' : 'x';
				int val = -alphabeta(depth - 1, -beta, -alpha, r[move], placeholder, placeholder);
				chess[i][j] = 0;
				if (val >= beta)
				{
					x = i;
					y = j;
					return beta;
				}
				if (val > alpha)
				{
					alpha = val;
					bestX = i;
					bestY = j;
				}
			}
		}
	}

	x = bestX;
	y = bestY;
	return alpha;
}

int evaluate(int move)
{
	if (xwin())
		return move ? -INF : INF;
	if (owin())
		return move ? INF : -INF;
	return 0;

	int xeva = 0, oeva = 0;
	int mask = (1 << (2 * SIZE + 2)) - 1;
	for (int i = 0; i < SIZE; i++)
	{
		for (int j = 0; j < SIZE; j++)
		{
			if (chess[j][i] == 'o') mask = ~((~mask) | (1 << j));
			if (chess[i][j] == 'o') mask = ~((~mask) | (1 << (SIZE + j)));
		}
		if (chess[i][i] == 'o') mask = ~((~mask) | (1 << (2 * SIZE)));
		if (chess[i][SIZE - 1 - i] == 'o') mask = ~((~mask) | (1 << (2 * SIZE + 1)));
	}
	xeva = count_ones(mask);

	mask = (1 << (2 * SIZE + 2)) - 1;
	for (int i = 0; i < SIZE; i++)
	{
		for (int j = 0; j < SIZE; j++)
		{
			if (chess[j][i] == 'x') mask = ~((~mask) | (1 << j));
			if (chess[i][j] == 'x') mask = ~((~mask) | (1 << (SIZE + j)));
		}
		if (chess[i][i] == 'x') mask = ~((~mask) | (1 << (2 * SIZE)));
		if (chess[i][SIZE - 1 - i] == 'x') mask = ~((~mask) | (1 << (2 * SIZE + 1)));
	}
	oeva = count_ones(mask);

	return move == 0 ? xeva - oeva : oeva - xeva;
}

int count_ones(int num)
{
	int ans = 0;

	while (num != 0)
	{
		if (num & 1)
		{
			ans++;
		}
		num >>= 1;
	}
	return ans;
}

void print_board()
{
	for (int i = 0; i < SIZE; i++)
	{
		for (int j = 0; j < SIZE; j++)
		{
			if (chess[i][j] == 0)
			{
				putchar('.');
			}
			else
			{
				putchar(chess[i][j]);
			}
		}
		putchar('\n');
	}
}